/*
 * The Smacker library was ported from C# for use in Silvie. The original
 * library is copyright Chris Toshok. It is released under an X11 license.
 */

package utils.smacker;

import java.io.IOException;

public class HuffmanTree {
	protected Node rootNode;

	/**
	 * Builds a new 8-bit huffmantree.
	 * 
	 * @param m The stream to build the tree from
	 * @see <a
	 *      href="http://wiki.multimedia.cx/index.php?title=Smacker#Packed_Huffman_Trees">Packed
	 *      Huffman Trees</a>
	 */
	public void buildTree(SmackerBitStream m) throws IOException {
		// Read tag
		int tag = m.readBits(1);
		// If tag is zero, finish
		if (tag == 0) {
			return;
		}
		// Init tree
		this.rootNode = new Node();
		buildTree(m, this.rootNode);
		// For some reason we have to skip a bit
		m.readBits(1);
	}

	/**
	 * Decodes a value using this tree based on the next bits in the specified
	 * stream
	 * 
	 * @param m The stream to read bits from
	 */
	public int decode(SmackerBitStream m) throws IOException {
		Node currentNode = this.rootNode;
		if (currentNode == null) {
			return 0;
		}
		while (!currentNode.isLeaf) {
			int bit = m.readBits(1);
			if (bit == 0) {
				currentNode = currentNode.getLeft();
			} else {
				currentNode = currentNode.getRight();
			}
		}
		return currentNode.getValue();
	}

	protected void buildTree(SmackerBitStream m, Node current) throws IOException {
		// Read flag
		int flag = m.readBits(1);
		// If flag is nonzero
		if (flag != 0) {
			// Advance to "0"-branch
			Node left = new Node();
			// Recursive call
			buildTree(m, left);
			// The first left-node is actually the root
			if (current == null) {
				this.rootNode = left;
				return;
			} else {
				current.setLeft(left);
			}
		} else { // If flag is zero
			if (current == null) {
				current = new Node();
				this.rootNode = current;
			}
			// Read 8 bit leaf
			int leaf = m.readBits(8);
			// Console.WriteLine("Decoded :" + leaf);
			current.isLeaf = true;
			current.setValue(leaf);
			return;
		}
		// Continue on the "1"-branch
		current.setRight(new Node());
		buildTree(m, current.getRight());
	}

	public void printTree() {
		this.rootNode.print();
	}
}

class BigHuffmanTree extends HuffmanTree {
	private HuffmanTree highByteTree;
	private HuffmanTree lowByteTree;
	private Node marker1;
	private Node marker2;
	private Node marker3;
	private int iMarker1;
	private int iMarker2;
	private int iMarker3;

	/**
	 * Decodes a value using this tree based on the next bits in the specified
	 * stream
	 * 
	 * @param m The stream to read bits from
	 */
	@Override
	public int decode(SmackerBitStream m) throws IOException {
		// int v = base.Decode(m);
		Node currentNode = super.rootNode;
		if (currentNode == null) {
			return 0;
		}
		while (!currentNode.isLeaf) {
			int bit = m.readBits(1);
			if (bit == 0) {
				currentNode = currentNode.getLeft();
			} else {
				currentNode = currentNode.getRight();
			}
		}
		int v = currentNode.getValue();
		if (v != this.iMarker1) {
			this.iMarker3 = this.iMarker2;
			this.iMarker2 = this.iMarker1;
			this.iMarker1 = v;
			this.marker3.setValue(this.marker2.getValue());
			this.marker2.setValue(this.marker1.getValue());
			this.marker1.setValue(v);
		}
		return v;
	}

	/**
	 * Resets the dynamic decoder markers to zero
	 */
	public void resetDecoder() {
		this.marker1.setValue(0);
		this.marker2.setValue(0);
		this.marker3.setValue(0);
		this.iMarker1 = 0;
		this.iMarker2 = 0;
		this.iMarker3 = 0;
	}

	@Override
	public void buildTree(SmackerBitStream m) throws IOException {
		// Read tag
		int tag = m.readBits(1);
		// If tag is zero, finish
		if (tag == 0) {
			return;
		}
		this.lowByteTree = new HuffmanTree();
		this.lowByteTree.buildTree(m);
		this.highByteTree = new HuffmanTree();
		this.highByteTree.buildTree(m);
		this.iMarker1 = m.readBits(16);
		// System.Console.WriteLine("M1:" + iMarker1);
		this.iMarker2 = m.readBits(16);
		// System.Console.WriteLine("M2:" + iMarker2);
		this.iMarker3 = m.readBits(16);
		// System.Console.WriteLine("M3:" + iMarker3);
		super.rootNode = new Node();
		buildTree(m, super.rootNode);
		// For some reason we have to skip a bit
		m.readBits(1);
		if (this.marker1 == null) {
			// System.Console.WriteLine("Not using marker 1");
			this.marker1 = new Node();
		}
		if (this.marker2 == null) {
			// System.Console.WriteLine("Not using marker 2");
			this.marker2 = new Node();
		}
		if (this.marker3 == null) {
			// System.Console.WriteLine("Not using marker 3");
			this.marker3 = new Node();
		}
	}

	@Override
	protected void buildTree(SmackerBitStream m, Node current) throws IOException {
		// Read flag
		int flag = m.readBits(1);
		// If flag is nonzero
		if (flag != 0) {
			// Advance to "0"-branch
			Node left = new Node();
			// Recursive call
			buildTree(m, left);
			// The first left-node is actually the root
			if (current == null) {
				super.rootNode = left;
				return;
			} else {
				current.setLeft(left);
			}
		} else { // If flag is zero
			if (current == null) {
				current = new Node();
				super.rootNode = current;
			}
			// Read 16 bit leaf by decoding the low byte, then the high byte
			int lower = this.lowByteTree.decode(m);
			int higher = this.highByteTree.decode(m);
			int leaf = lower | (higher << 8);
			// System.Console.WriteLine("Decoded: " + leaf);
			// If we found one of the markers, store pointers to those nodes.
			if (leaf == this.iMarker1) {
				leaf = 0;
				this.marker1 = current;
			}
			if (leaf == this.iMarker2) {
				leaf = 0;
				this.marker2 = current;
			}
			if (leaf == this.iMarker3) {
				leaf = 0;
				this.marker3 = current;
			}
			current.isLeaf = true;
			current.setValue(leaf);
			return;
		}
		// Continue on the "1"-branch
		current.setRight(new Node());
		buildTree(m, current.getRight());
	}
}

class Node {
	// "0"- branch
	private Node left;
	// "1"-branch
	private Node right;
	// Made public for more speed
	public boolean isLeaf;
	private int value;

	public Node getLeft() {
		return this.left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return this.right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public int getValue() {
		return this.value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public void print(String prefix) {
		System.out.println(prefix + (this.isLeaf ? "Leaf: " + this.value : "No Leaf"));
		if (this.left != null) {
			this.left.print(prefix + " L:");
		}
		if (this.right != null) {
			this.right.print(prefix + " R:");
		}
	}

	public void print() {
		print("");
	}
}
